package com.code.test.first.greedy;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.md
 * <p>
 * 给定一个非负整数数组，你最初位于数组的第一个位置。
 * <p>
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * <p>
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 * <p>
 * 示例:
 * <p>
 * 输入: [2,3,1,1,4]
 * 输出: 2
 * 解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳  1  步，然后跳  3  步到达数组的最后一个位置。
 * 说明: 假设你总是可以到达数组的最后一个位置。
 */
public class Code45 {

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 1, 4};
        int ret = jump(nums);
        System.out.println(ret);
    }

    /**
     * 想要最少次数跳到末尾，需要每一步都跳得尽可能远
     * 如何才能每一步都跳得最远呢？每一个位置都有可跳的距离
     * 要跳得最远，需要在这个可跳距离范围内取最大值，i+nums[i]最大
     * i+ nums[i]解释：
     * i：代表当前下标
     * nums[i]:代表这个下标的值，这个值是能跳的距离
     * 所以 i+nums[i] 代表从当前下标能跳的范围是多少
     */

    public static int jump(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }

        int step = 0;
        int curDistance = 0;
        int maxDistance = 0;
        for (int i = 0; i < nums.length; i++) {
            //在可覆盖区域内更新最大的覆盖区域
            maxDistance = Math.max(maxDistance, i + nums[i]);
            //说明当前一步，再跳一步就到达了末尾
            if (maxDistance >= nums.length - 1) {
                step++;
                break;
            }
            //走到当前覆盖的最大区域时，更新下一步可达的最大区域
            if (i == curDistance) {
                step++;
                curDistance = maxDistance;
            }
        }
        return step;
    }

    /**
     * 想要最少次数跳到末尾，需要每一步都跳得尽可能远
     * 如何才能每一步都跳得最远呢？每一个位置都有可跳的距离
     * 要跳得最远，需要在这个可跳距离范围内取最大值，i+nums[i]最大
     * ----
     * 以下解法符合以上思路，但效率不高，有while及for循环，O(nlogn)
     * https://juejin.cn/post/7111127356416196644
     */
    public static int jump2(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int tail = 0;
        int step = 0;

        //下标加元素值还没法到达数组末尾，继续往下走
        while (tail + nums[tail] < nums.length - 1) {
            int targetIndex = 0;
            int max = 0;
            //从下标开始，遍历到当前可达的最远距离，找出这个范围内的最远距离
            for (int i = tail; i <= tail + nums[tail]; i++) {
                //找出最远可跳距离以及对应的元素下标
                if (i + nums[i] > max) {
                    max = i + nums[i];
                    targetIndex = i;
                }
            }
            tail = targetIndex;
            step++;

        }
        return step;
    }
}
